//
// Created by xili on 2024/8/7 19:09.
// Go big or go home.
//
#include <vector>
#include <unordered_set>
#include <queue>
#include <functional>

using namespace std;

//优先队列
class Solution1 {
public:
    int nthUglyNumber(int n) {
        vector<int> factors = {2, 3, 5};
        unordered_set<long> seen;
        priority_queue<long, vector<long>, greater<long>> heap;
        seen.insert(1L);
        heap.push(1L);
        int ugly = 0;
        for (int i = 0; i < n; i++) {
            long curr = heap.top();
            heap.pop();
            ugly = (int) curr;
            for (int factor: factors) {
                long next = curr * factor;
                if (!seen.count(next)) {
                    seen.insert(next);
                    heap.push(next);
                }
            }
        }
        return ugly;
    }
};

//动态规划 三指针
class Solution2 {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n + 1);
        dp[1] = 1;
        for (int i = 2, i2 = 1, i3 = 1, i5 = 1; i <= n; i++) {
            int a = dp[i2] * 2;
            int b = dp[i3] * 3;
            int c = dp[i5] * 5;
            int cur = min({a, b, c});
            i2 += cur == a;
            i3 += cur == b;
            i5 += cur == c;
            dp[i] = cur;
        }
        return dp[n];
    }
};